package com.sheng.leetcode.year2025.month10.day05;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * @author by ls
 * @date 2025/10/14
 * <p>
 * 417. 太平洋大西洋水流问题<p>
 * <p>
 * 有一个 m × n 的矩形岛屿，与 太平洋 和 大西洋 相邻。 “太平洋” 处于大陆的左边界和上边界，而 “大西洋” 处于大陆的右边界和下边界。<p>
 * 这个岛被分割成一个由若干方形单元格组成的网格。给定一个 m x n 的整数矩阵 heights ， heights[r][c] 表示坐标 (r, c) 上单元格 高于海平面的高度 。<p>
 * 岛上雨水较多，如果相邻单元格的高度 小于或等于 当前单元格的高度，雨水可以直接向北、南、东、西流向相邻单元格。水可以从海洋附近的任何单元格流入海洋。<p>
 * 返回网格坐标 result 的 2D 列表 ，其中 result[i] = [ri, ci] 表示雨水从单元格 (ri, ci) 流动 既可流向太平洋也可流向大西洋 。<p>
 * <p>
 * 示例 1：<p>
 * 输入: heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]<p>
 * 输出: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]<p>
 * <p>
 * 示例 2：<p>
 * 输入: heights = [[2,1],[1,2]]<p>
 * 输出: [[0,0],[0,1],[1,0],[1,1]]<p>
 * <p>
 * 提示：<p>
 * m == heights.length<p>
 * n == heights[r].length<p>
 * 1 <= m, n <= 200<p>
 * 0 <= heights[r][c] <= 10^5<p>
 */
public class LeetCode0417 {

    @Test
    public void test01() {
        int[][] heights = {{1, 2, 2, 3, 5}, {3, 2, 3, 4, 4}, {2, 4, 5, 3, 1}, {6, 7, 1, 4, 5}, {5, 1, 1, 2, 4}};
//        int[][] heights = {{2, 1}, {1, 2}};
        List<List<Integer>> lists = new Solution().pacificAtlantic(heights);
        System.out.println(new Solution().pacificAtlantic(heights));
    }
}

class Solution {
    List<List<Integer>> lists = new ArrayList<>();
    int[][] arrs;
    int m, n;
    int[][] dirs = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        arrs = heights;
        m = heights.length;
        n = heights[0].length;
        boolean[][] b1 = new boolean[m][n], b2 = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 || j == 0) {
                    if (!b1[i][j]) {
                        dfs(i, j, b1);
                    }
                }
                if (i == m - 1 || j == n - 1) {
                    if (!b2[i][j]) {
                        dfs(i, j, b2);
                    }
                }
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (b1[i][j] && b2[i][j]) {
                    List<Integer> integers = new ArrayList<>();
                    integers.add(i);
                    integers.add(j);
                    lists.add(integers);
                }
            }
        }
        return lists;
    }

    public void dfs(int i, int j, boolean[][] b) {
        b[i][j] = true;
        for (int[] dir : dirs) {
            int diri = i + dir[0], dirj = j + dir[1];
            if (diri < 0 || diri >= m || dirj < 0 || dirj >= n) {
                continue;
            }
            if (b[diri][dirj] || arrs[diri][dirj] < arrs[i][j]) {
                continue;
            }
            dfs(diri, dirj, b);
        }
    }
}
